The notion of a shuffle of a collection of objects, records, or tokens is simple and intuitive, and useful examples abound in various daily human activities. A gambler in a casino knows that when he picks up his hand of cards, each one will be one of 52 unique values, and that no one else at the table will have duplicates of the ones he holds. He does not, however, have any knowledge of how the cards are distributed, even though he may have recorded the exact card order before they were shuffled by the dealer.
In the context of electronic data, the problem of achieving the same kind of random, yet verifiable permutation of an input sequence is surprisingly difficult. The problem is that the data itself is either always visible to the auditor, or it isn't. If it is, then the correspondence between input records and output records is trivial to reconstruct by the auditor or other observer. If it isn't, then input and output records must be different representations of the same underlying data. But if the output is different enough (that is, encrypted well enough) that the auditor cannot reconstruct the correspondence, then how can the auditor be sure that the shuffler did not change the underlying data in the process of shuffling?
Most of the description below is devoted to giving an efficient (linear) method for solving this problem in an important context—ElGamal encrypted data. In order to make the exposition as clear and concise as possible, the majority of the description below explicitly refers to the specific case where operations are carried out in Z*p, the multiplicative group of units modulo a large prime, p. However, the only properties of the underlying (multiplicative) group used is that the associated ElGamal cryptosystem should be secure, and that the Chaum-Pedersen protocol for the relation loggX=loghY=u (D. Chaum. Zero-knowledge undeniable signatures. Advances in Cryptology—EUROCRYPT '90, Lecture Notes in Computer Science, volume 473, pages 458-464, Springer-Verlag, 1991. D. Chaum and T. P. Pedersen. Wallet Databases With Observers. In Advances in Cryptology—CRYPTO'92, Volume 740 of Lecture Notes in Computer Science, pages 89-105, Berlin, 1993. Springer-Verlag.) should not leak information about the secret exponent, u. In fact, for one embodiment, a universally verifiable, multi-authority election protocol—the verifier will be implemented via the Fiat-Shamir heuristic (A. Fiat, A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. Advances in Cryptology—CRYPTO '86, Lecture Notes in Computer Science, pp. 186-194, Springer-Verlag, New York, 1987.), so in this case it is sufficient that the protocol be zero-knowledge against an honest verifier. (R. Cramer, R. Gennaro, B. Schoenmakers. A secure and optimally efficient multi-authority election scheme. Advances in Cryptology—EUROCRYPT '97, Lecture Notes in Computer Science, Springer-Verlag, 1997.) Thus, the shuffle protocol is also useful when the ElGamal cryptosystem is implemented over other groups such as elliptic curves. The general Boolean proof techniques of R. Cramer, I. Damgrd, B. Schoenmakers, Proofs of partial knowledge and simplified design of witness hiding protocols (Advances in Cryptology—CRYPTO '94, Lecture Notes in Computer Science, pp. 174-187, Springer-Verlag, Berlin, 1994.), can also be used to construct a proof with the same properties, however, the resulting proof size (complexity) is quadratic, or worse, in the size of the input sequence.
The protocols or methods described below also offer several advantages over the cut-and-choose technique as used in K. Sako, J. Kilian. Receipt-free mix-type voting scheme—A practical solution to the implementation of a voting booth, Advances in Cryptology—EUROCRYPT '95, Lecture Notes in Computer Science, Springer-Verlag, 1995. In this approach, the size of the proof is dependent on the probability of a cheating prover that is required to satisfy all participants. In the shuffle protocol described herein, this cheating probability is essentially k/q, where k is the number of elements to be shuffled, and q is the size of the subgroup of Z*p in which the elements are encrypted. Although no analysis of the proof size is done in the K. Sako paper, it appears that, in order to obtain similarly low cheating probability, it will need to be orders of magnitude larger than the size of the proof provided herein. (Moreover, if the K. Sako protocol is implemented non-interactively, the cheating probability would need to be chosen exceedingly small, because a malicious participant might use considerable off-line computation to generate a forged proof by exhaustive search. This of course, could be the case with the protocols described, but the probability k/q is, for all practical values of k and q, certainly small enough.)
The advantage of the current scheme becomes even more apparent when seen in the context of the resulting universally verifiable election protocol. In K. Sako, each voter must interact sequentially with each “counting center” before actually casting his/her vote. On this account, it is unlikely that a useable implementation could be built for large scale, public sector elections in the near future. In contrast, protocols described below, put all authority participation (except, possibly, for the creation of basic election parameters) at the close of the election, purely for the purpose of tabulation.
This nice property is also found in the elegant homomorphic election protocol in the paper by R. Cramer, R. Gennaro, and B. Schoenmakers. However, that protocol can only be applied to ballots whose questions are of a simple “choose (at most) m of n” type. This effectively precludes “write-in” responses, as well as “proportional type” questions where the voter is expected to indicate answers in preferential order, and questions are tabulated in accordance with this preference. A couple of somewhat less important disadvantages of the R. Cramer, R. Gennaro, and B. Schoenmakers scheme are that it expands vote data size considerably, and that it requires a voter validity proof. This proof further expands the vote data size by about an order of magnitude, and is unattractive from a practical perspective, because it presumes special purpose code to be running on the voter's computer.
The protocol is described below constructed entirely from a sequence of Chaum-Pedersen proofs, and elementary arithmetic operations. It is thus simple to implement.
In the drawings, identical reference numbers identify identical or substantially similar elements or acts. To easily identify the discussion of any particular element or act, the most significant digit or digits in a reference number refer to the Figure number in which that element is first introduced (e.g., element 204 is first introduced and discussed with respect to FIG. 2).
The headings provided herein are for convenience only and do not necessarily affect the scope or meaning of the claimed invention.